הרצאה 8 - רשימת דילוגים
רשימת דילוגים (skip list):
- הוא מימוש של dynamic set עם הסיבוכיות זמן הבאות:
- חיפוש והכנסה :
- מחיקה:
- מינימום, מקסימום, Successor (יורש), Predecessor (קודם):
- חיפוש והכנסה :
מבנה הרשימה:
- רשימת דילוגים S מכילה
רשימה מקושרת דו כיוונית ממויינת כך ש: - הרשימה
מכילה את כל האיברים של S - הרשימה
מכילה את כל האיברים של בהסתברות של 0.5 - כל רשימה מכילה תא סנטינל שמחזיק מצביע לאלמנט הראשון של אותה רשימה (והאלמנט הראשון מחזיק מצביע לסנטינל).
- במקום לשמור מספר תאים (Nodes) עבור כל איבר של S, שומרים רק תא אחד עבור כל איבר, כאשר לכל תא יש את הערכים הבאים:
- המפתח(x.key)
- הגובה(x.h): מוגדר כ i המקסימלי שעבורו x שייך ל
- מערך(x.next): מערך בגודל h + 1 שמכיל מצביעים לתאים שבאים אחרי x ברשימות
- מערך (x.prev): בערך בגודל h +1
- גובה הרשימה: הגובה של הסנטינל, הוא גם הגובה המקסימלי של שאר התאים.

- הרשימה
הגודל הצפוי (תוחלת גודל הרשימה):
- תוחלת מספר התאים ברשימת דילוגים המכילה n איברים (לא כולל תאי סנטינל) היא 2n.
- הרעיון המרכזי:
- ההסתברות שאיבר מסוים
יופיע ברמה היא . - גודל הרמה
(מספר האיברים בה) מתפלג בינומית עם הפרמטרים ו- ולכן תוחלת מספר האיברים ברמה היא: . - תוחלת מספר הצמתים הכולל מתקבלת מסכום התוחלות של כל הרמות (מ-
עד ): -
- ההסתברות שאיבר מסוים
הגובה הצפוי (תוחלת גובה הרשימה):
- תוחלת הגובה של רשימת הדילוגים היא לכל היותר
. - הרעיון המרכזי:
-
מגדירים משתנה מקרי מציין (Indicator)
לכל רמה , המקבל את הערך אם הרמה אינה ריקה, ו- אם היא ריקה. -
גובה הרשימה
הוא סכום המשתנים המציינים: . -
מכיוון ש-
, מתקיים . כמו כן, מכיוון ש- , מתקיים תמיד . -
מפצלים את סכום התוחלות לשני חלקים – עד הרמה ה-
, וממנה והלאה (מכיוון ש אם נציב בתוחלת מספר האיברים, נקבל שתוחלת מספר האיברים ברמה הזו היא בדיוק: ): - בחלק הראשון (עד
) חוסמים את התוחלת ב- (מקסימום רמות). - בחלק השני (מרמה
ואילך) משתמשים בחסם , וסכום הטור ההנדסי שמתקבל חסום ב- .
- בחלק הראשון (עד
-
סה"כ מקבלים:
.
-
הגודל הצפוי (כולל זקיפים):
- תוחלת מספר הצמתים הכולל ברשימה (כולל צמתי הזקיף) היא
. - הרעיון המרכזי:
- מספר הצמתים הרגילים בתוחלת הוא
. - בכל רמה יש סנטינל אחד. מכיוון שתוחלת הגובה חסומה ב-
, תוחלת מספר הסנטינלים חסומה ב- (כולל רמת הבסיס). - לכן, תוספת הסנטינלים לגודל הרשימה היא בסדר גודל של
, והגודל הכולל נשאר ליניארי: .
- מספר הצמתים הרגילים בתוחלת הוא